UVa/12318 - Digital Roulette/12318.3.cpp

   1 // Code written by Andrés Mejía
   2 using namespace std;
   3 #include <iostream>
   4 #include <vector>
   5 #include <set>
   6
   7 int main(){
   8     int n, m;
   9     while (cin >> n >> m) {
  10         if (n == 0 and m == 0) break;
  11         int k; cin >> k;
  12         vector<int> a(k + 1);
  13         // Read coefficients
  14         for (int i = 0; i < k + 1; ++i) {
  15             cin >> a[i];
  16         }
  17         int mod = n + 1;
  18         set<int> ans;
  19
  20         // Brute force on x
  21         for (int x = 0; x <= m; x++){
  22             // calculate P(x) and store the result in y
  23             int y = 0, d = 1;
  24             for (int i = 0; i < a.size(); ++i) {
  25                 // At this point, d == (x^i) % mod
  26                 y = (y + 1LL * a[i] * d) % mod; // the 1LL is to use long longs in the multiplication
  27                 d = (1LL * d * x) % mod;
  28             }
  29             ans.insert(y);
  30         }
  31         cout << ans.size() << endl;
  32     }
  33     return 0;
  34 }